<!DOCTYPE html>
<html>
<head>
	<title>Merge Sort Tree</title>
	<style>
		body {
			margin: 0;
			padding: 0;
			background-color: #EEE;
			font-family: Arial, sans-serif;
		}

		.tree {
			position: absolute;
			top: 50%;
			left: 50%;
			transform: translate(-50%, -50%);
			display: flex;
			align-items: center;
			justify-content: center;
			flex-direction: column;
			height: 500px;
			width: 100%;
			overflow: hidden;
		}

		.node {
			display: flex;
			align-items: center;
			justify-content: center;
			border: 1px solid #DDD;
			border-radius: 50%;
			height: 50px;
			width: 50px;
			background-color: #FFF;
			font-size: 20px;
			font-weight: bold;
			transition: background-color 0.5s ease;
		}

		.node.active {
			background-color: #F00;
			color: #FFF;
		}

		.line {
			position: absolute;
			border: 1px solid #DDD;
			height: 20px;
			width: 50%;
			top: 50%;
			left: 50%;
			transform: translate(-50%, -50%);
			z-index: -1;
			transition: background-color 0.5s ease;
		}

		.line.active {
			background-color: #F00;
		}
	</style>
</head>
<body>
	<div class="tree">
		<div class="node"></div>
		<div class="line"></div>
	</div>

	<script>
		const tree = document.querySelector('.tree');
		const rootNode = createNode(50, true);
		tree.appendChild(rootNode);

		// 创建节点
		function createNode(value, isRoot = false) {
			const node = document.createElement('div');
			node.classList.add('node');
			node.innerText = value;
			if (!isRoot) {
				const line = document.createElement('div');
				line.classList.add('line');
				tree.appendChild(line);
				node.line = line;
			}
			return node;
		}

		// 动画显示排序过程
		async function animateSort(node) {
			node.classList.add('active');
			await new Promise(resolve => setTimeout(resolve, 1000));
			node.classList.remove('active');
		}

		// 动画显示归并过程
		async function animateMerge(leftNode, rightNode, line) {
			leftNode.classList.add('active');
			rightNode.classList.add('active');
			line.classList.add('active');
			await new Promise(resolve => setTimeout(resolve, 1000));
			leftNode.classList.remove('active');
			rightNode.classList.remove('active');
			line.classList.remove('active');
		}

		// 归并排序
		async function mergeSort(node) {
			if (node.children.length === 1) {
				await animateSort(node.children[0]);
				return [node.children[0].innerText];
			}

			const middle = Math.floor(node.children.length / 2);
			const leftNode = node.children[0];
			const rightNode = node.children[1];
			const line = rightNode.line;

			const leftArray = await mergeSort(leftNode);
			const rightArray = await mergeSort(rightNode);
		await animateMerge(leftNode, rightNode, line);

		const result = [];
		let i = 0, j = 0;
		while (i < leftArray.length && j < rightArray.length) {
			if (leftArray[i] < rightArray[j]) {
				result.push(leftArray[i++]);
			} else {
				result.push(rightArray[j++]);
			}
		}

		while (i < leftArray.length) {
			result.push(leftArray[i++]);
		}

		while (j < rightArray.length) {
			result.push(rightArray[j++]);
		}

		node.removeChild(leftNode);
		node.removeChild(rightNode);

		const resultNode = createNode(result.join(' '));
		node.appendChild(resultNode);

		await animateSort(resultNode);

		return result;
	}

	// 初始化数据并进行排序
	const data = [20, 10, 50, 30, 40];
	const leafNodes = data.map(value => createNode(value));
	leafNodes.forEach(node => rootNode.appendChild(node));
	mergeSort(rootNode);
</script>
</body>
</html>